# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        robDict = {}
        unrobDict = {}

        def fun(root, rob):
            if root==None: return 0
            if rob:
                if id(root) in robDict: return robDict[id(root)]
                cnt = root.val + fun(root.left, False) + fun(root.right, False)
                robDict.update({id(root):cnt})
                return cnt
            else:
                if id(root) in unrobDict: return unrobDict[id(root)]
                cnt = max(fun(root.left, True), fun(root.left, False)) + max(fun(root.right, True), fun(root.right, False))
                unrobDict.update({id(root):cnt})
                return cnt
        ret = max(fun(root, True), fun(root, False))
        return ret

root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = None
root.left.right = TreeNode(3)
root.right.left = None
root.right.right = TreeNode(1)

print(Solution().rob(root))